package Hot_100;

import java.util.*;
/*
    给定一个二叉树的根节点 root ，返回它的中序遍历。
* */

public class T94_inorderTraversal {
    //--------------------- 法3 Morris ----------------------------------
    // 基本思想就是将二叉树装成一个链表，让左子树最右结点连接到根结点，这也是按照中序遍历的结果
    // 相比较于递归和迭代方法，它的空间复杂度为O(1);由于每个结点都会被来回遍历两次。所以时间复杂度为O(2*n)=O(n)
    // 可以结合力扣官方的动图来理解
    public List<Integer> inorderTraversal_3(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();    //存储中序遍历的结果序列
        if (root == null) {
            return list;
        }

        TreeNode predecessor = null;
        while (root != null) {
            if (root.left != null) {             //如果有左孩子
                predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root) { //predecessor:定位到root的左子树的最右结点
                    predecessor = predecessor.right;
                }

                if (predecessor.right == null) { //如果为空，将左子树的最右结点的右指针连接到该子数的根结点
                    predecessor.right = root;
                    root = root.left;            //继续遍历左子树

                } else {                         //如果不为空，说明左子树已经遍历完成
                    list.add(root.val);
                    predecessor.right = null;    //其实这里不置空也没有影响的
                    root = root.right;           //实际是遍历root的父节点，在前面它的右指针被修改
                }
            } else {                             //如果没有左孩子,直接遍历右子树 (或者是遍历root的父节点，只是在前面它的右指针被修改)
                list.add(root.val);
                root = root.right;
            }
        }
        return list;
    }


    //--------------------- 法2 迭代----------------------------------
    public List<Integer> inorderTraversal_2(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();    //存储中序遍历的结果序列
        if (root == null) {
            return list;
        }

        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) { //root!=null只是第一次作为进入循环的判断条件，后面直接看的是!stack.isEmpty()
            // 先根入栈再将所有子孙左结点入栈
            while (root != null) { //第一次循环，将该结点及其子孙的左结点入栈；之后的循环，对应上一轮出栈结点，如果它没有右孩子，也就不会执行该段代码，否则压栈会压入重复的元素
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();        //取出栈顶元素
            list.add(root.val);        //记录中序遍历的结果
            root = root.right;         //指向其右结点，如果存在右结点则在下轮循环会继续遍历其右结点的左子孙结点并将其入栈；
                                       //如果不存在右节点则下轮循环就继续弹出栈顶元素进行遍历
        }
        return list;
    }

// --------------------- 法1 递归----------------------------------
    public List<Integer> inorderTraversal_1(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();    //存储中序遍历的结果序列
        if (root == null) {
            return list;
        }
        inorder(root,list);
        return list;
    }

    void inorder(TreeNode Node, ArrayList<Integer> list) {
        if (Node == null) {
            return;
        }
        inorder(Node.left, list);
        list.add(Node.val);
        inorder(Node.right, list);
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}